Backoff Design: Fundamental Tradeoff and Design Criterion

　

Binary Exponential Backoff (BEB) is a key component of the IEEE 802.11 DCF protocol. It has been shown that BEB can achieve the theoretical limit of throughput as long as the initial backoff window size is properly selected. It, however, suffers from significant delay degradation when the network becomes saturated. It is thus of special interest for us to further design backoff schemes for IEEE 802.11 DCF networks that can achieve comparable throughput as BEB, but provide better delay performance.

This paper presents a systematic study on the effect of backoff schemes on throughput and delay performance of saturated IEEE 802.11 DCF networks. In particular, a backoff scheme is defined as a sequence of backoff window sizes {Wi}. The analysis shows that a saturated IEEE 802.11 DCF network has a single steady-state operating point as long as {Wi} is a monotonic increasing sequence. The maximum throughput is found to be independent of {Wi}, yet the growth rate of {Wi} determines a fundamental tradeoff between throughput and delay performance. For illustration, Polynomial Backoff is proposed, and the effect of polynomial power x on the network performance is characterized. It is demonstrated that Polynomial Backoff with a larger x is more robust against the fluctuation of the network size, but in the meanwhile suffers from a larger second moment of access delay. Quadratic Backoff (QB), i.e., Polynomial Backoff with x=2, stands out to be a favorable option as it strikes a good balance between throughput and delay performance. The comparative study between QB and BEB confirms that QB well preserves the robust nature of BEB and achieves much better queueing performance than BEB.